home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / drdobbs / ddjcompr / compact / compact.c < prev    next >
C/C++ Source or Header  |  1990-11-05  |  41KB  |  2,378 lines
  1. /******************************************************************
  2.  *    ex:se ts=4 sw=4 ai:
  3.  *
  4.  *    Data compression program.
  5.  *
  6.  *    Author: Gene H. Olson
  7.  *            Smartware Consulting
  8.  *
  9.  *    This is FREE software in the PUBLIC DOMAIN.
  10.  *
  11.  *    This program may be used only for research into data
  12.  *    compression techniques. See WARNING in compact(1)
  13.  *    manual page for further discussion.
  14.  *
  15.  *    "Everything FREE contains no guarantee."
  16.  ********************************************************************/
  17.  
  18. #define VERSION "compact version 1.0 PL0"
  19.  
  20. #ifndef lint
  21. static char sccs[] = "@(#)compact.c    1.25 10/28/90" ;
  22. #endif
  23.  
  24. #include <sys/lock.h>
  25.  
  26. #include <fcntl.h>
  27. #include <stdio.h>
  28. #include <ctype.h>
  29. #include <assert.h>
  30. #include <signal.h>
  31.  
  32. #if MARK
  33. # include <prof.h>
  34. #else
  35. # define MARK(x)
  36. #endif
  37.  
  38. extern void exit() ;
  39. extern char *memset() ;
  40. extern char *memcpy() ;
  41.  
  42. extern char *share_create() ;
  43. extern char *share_open() ;
  44.  
  45. #ifndef DEBUG
  46. #    ifdef lint
  47. #        define DEBUG 99
  48. #    else
  49. #        define DEBUG 0
  50. #    endif
  51. #endif
  52.  
  53. #ifndef CHECK
  54. #    if DEBUG >= 2
  55. #        define CHECK 100
  56. #    else
  57. #        define CHECK 0
  58. #    endif
  59. #endif
  60.  
  61. /*
  62.  *    Pet typedefs.
  63.  */
  64.  
  65. #define SWAP(x) (((ushort)(x) >> 8) | ((ushort)(x) << 8))
  66.  
  67. #define uchar    unsigned char
  68. #define    ushort    unsigned short
  69. #define ulong    unsigned long
  70.  
  71. #if lint
  72. #define malloc(x)        0
  73. #define realloc(x,y)    0
  74. #endif
  75.  
  76. /*
  77.  *    Fundamental constants.
  78.  */
  79.  
  80. #define MAGIC        0xc5a3        /* Magic number */
  81. #define ODDMAGIC    0xc3a4        /* EOF magic for odd files */
  82. #define EVENMAGIC    0xc3a5        /* EOF magic for even files */
  83.  
  84. #define MAXCHAR ((1 << 16) + 1)    /* Size of character set */
  85.  
  86. /*
  87.  *    Tuning parameter defaults.
  88.  */
  89.  
  90. #define    MEMORY    0x40000000        /* Default bytes memory */
  91. #define INRUN    10000000        /* Default bytes input run */
  92.  
  93. #ifndef HASHRATIO
  94. #define    HASHRATIO    1.2            /* Ratio of hash entries to items */
  95. #endif
  96.  
  97. /*
  98.  *    Compression item table definition.
  99.  */
  100.  
  101. #define    HASHFUN(prefix, suffix) \
  102.     ((((((prefix) << 3) + (suffix)) << 4) - (prefix) + (suffix)) & (hashmask))
  103.  
  104. typedef struct h_struct ITEM ;
  105.  
  106. struct h_struct
  107. {
  108.     ITEM*    h_next ;            /* Next item on hash list */
  109.     ITEM**    h_last ;            /* Link ptr to this item */
  110.     ulong    h_code ;            /* Previous code */
  111.     ushort    h_char ;            /* Current input character */
  112.     ushort    h_ref ;                /* Reference flag */
  113. } ;
  114.  
  115. int hashsize ;                    /* Hash table size (power 2) */
  116.  
  117. int maxitem ;                    /* Maximum item number */
  118.  
  119. /*
  120.  *    Decompression item table definition.
  121.  */
  122.  
  123. typedef struct d_struct DEC ;
  124.  
  125. struct d_struct
  126. {
  127.     ulong    d_code ;            /* Decompression code */
  128.     ushort    d_char ;            /* Decompression character */
  129.     ushort    d_ref ;                /* Reference flag */
  130. } ;
  131.  
  132. /*
  133.  *    Caught signal list.
  134.  */
  135.  
  136. int sig[] = { SIGHUP, SIGINT, SIGQUIT, SIGPIPE, SIGTERM, 0 } ;
  137.  
  138. /*
  139.  *    Debugging stuff.
  140.  */
  141.  
  142. #if DEBUG >= 1
  143. int debug ;                        /* Debug level */
  144. #endif
  145.  
  146. /*
  147.  *    Efficiency checks.
  148.  */
  149.  
  150. #if DEBUG >= 1
  151. long collision ;
  152. #endif
  153.  
  154. /*
  155.  *    User parameters.
  156.  */
  157.  
  158. int action ;                    /* c==compact or e==expand */
  159.  
  160. char *infname ;                    /* Input file name */
  161. char *outfname ;                /* Output file name */
  162.  
  163. int infd ;                        /* Input file descriptor */
  164. int outfd ;                        /* Output file descriptor */
  165.  
  166. long inrun ;                    /* Maximum input run length */
  167.  
  168. long memory ;                    /* Memory to use */
  169. long maxwidth ;                    /* Max width of output code */
  170.  
  171. int quiet ;                        /* Quiet mode */
  172.  
  173. int inbs ;                        /* Input block size */
  174. int outbs ;                        /* Output block size */
  175.  
  176. int phys ;                        /* Output physical record size */
  177.  
  178. int insize ;                    /* Input volume size (records) */
  179. int outsize ;                    /* Output volume size (records) */
  180.  
  181. ulong inrec ;                    /* Input record number */
  182. ulong outrec ;                    /* Output record number */
  183.  
  184. int incopy ;                    /* Read input to non-shared buffer */
  185. int outcopy ;                    /* Write output from non-shared buffer */
  186.  
  187. int inswap ;                    /* Swap input bytes */
  188. int outswap ;                    /* Swap output bytes */
  189.  
  190. int memlock ;                    /* Lock process into memory */
  191.  
  192. int intank ;                    /* Number of input buffers */
  193. int outtank ;                    /* Number of output buffers */
  194.  
  195. int inpid ;                        /* Input tank process PID */
  196. int outpid ;                    /* Output tank process PID */
  197.  
  198. int (*getin)() ;                /* Get input routine */
  199. int (*putout)() ;                /* Put output routine */
  200.  
  201. char *acommand ;                /* Medium setup command */
  202. char *zcommand ;                /* Medium teardown command */
  203.  
  204. char *rsh ;                        /* Read share structure (opaque) */
  205. char *wsh ;                        /* Write share structure (opaque) */
  206.  
  207. /*
  208.  *    Miscellaneous declarations.
  209.  */
  210.  
  211. int invol ;                        /* Input volume number */
  212. int outvol ;                    /* Output volume number */
  213.  
  214. ushort *inbuf ;                    /* Input buffer */
  215. ushort *outbuf ;                /* Output buffer */
  216.  
  217. ushort *lastbuf ;                /* Last buffer read by inprocess */
  218. int lastcount ;                    /* Corresponding buffer count */
  219.  
  220. ulong intotal ;                    /* Input character count */
  221. ulong outtotal ;                /* Output character count */
  222.  
  223. ushort eofmagic ;                /* EOF magic number */
  224.  
  225.  
  226.  
  227. /**************************************************************
  228.  *    quit - Exit gracefully.
  229.  **************************************************************/
  230.  
  231. void
  232. quit(s)
  233. int s ;
  234. {
  235.     register int i ;
  236.     register int pid ;
  237.     int rs ;
  238.  
  239.     for (i = 0 ; sig[i] ; i++) (void) signal(sig[i], SIG_IGN) ;
  240.  
  241.     /*
  242.      *    Close shared memory.
  243.      */
  244.  
  245.     if (rsh) share_close(rsh) ;
  246.     if (wsh) share_close(wsh) ;
  247.  
  248.     /*
  249.      *    Wait for inprocess and outprocess to complete.
  250.      */
  251.  
  252.     while (inpid | outpid)
  253.     {
  254.         pid = wait(&rs) ;
  255.         if (pid == -1) break ;
  256.         if (inpid == pid)
  257.         {
  258.             inpid = 0 ;
  259.             if (s == 0) s = rs ;
  260.         }
  261.         if (outpid == pid)
  262.         {
  263.             outpid = 0 ;
  264.             if (s > 0) s = rs ;
  265.         }
  266.     }
  267.     
  268.     /*
  269.      *    Destroy allocated shared memory.
  270.      */
  271.  
  272.     if (rsh) share_destroy(rsh) ;
  273.     if (wsh) share_destroy(wsh) ;
  274.  
  275.     /*
  276.      *    Execute final teardown command.
  277.      *
  278.      *    Note that if we were in compress mode with
  279.      *    multi-volume input, the zcommand has already
  280.      *    been done by the input() routine when prompting
  281.      *    for the last volume of the set.
  282.      */
  283.  
  284.     if (s == 0 && zcommand && !(action == 'c' && insize))
  285.         (void) system(zcommand) ;
  286.  
  287.     exit(s) ;
  288. }
  289.  
  290.  
  291.  
  292. /***********************************************************
  293.  *    getval - Get value
  294.  ***********************************************************/
  295.  
  296. long
  297. getval(cp, units)
  298. register char *cp ;
  299. int units ;
  300. {
  301.     register int val ;
  302.  
  303.     units = 0 ;
  304.  
  305.     if (!isdigit(*cp)) return(-1) ;
  306.  
  307.     val = 0 ;
  308.     do
  309.     {
  310.         val *= 10 ;
  311.         val += *cp++ - '0' ;
  312.     } while (isdigit(*cp)) ;
  313.  
  314.     if (*cp) units = *cp++ ;
  315.  
  316.     switch (units)
  317.     {
  318.         case 'B':
  319.         case 'b':
  320.             val *= 512 ;
  321.             break ;
  322.  
  323.         case 'K':
  324.         case 'k':
  325.             val *= 1024 ;
  326.             break ;
  327.  
  328.         case 'M':
  329.         case 'm':
  330.             val *= 1000 * 1024 ;
  331.             break ;
  332.         
  333.         case 0:
  334.             break ;
  335.         
  336.         default:
  337.             return(-1) ;
  338.     }
  339.  
  340.     return (*cp==0 ? val : -1) ;
  341. }
  342.  
  343.  
  344.  
  345. /************************************************************
  346.  *    confirm - Wait for volume load confirmation.
  347.  ************************************************************/
  348.  
  349. confirm()
  350. {
  351.     register int n ;
  352.     char ch ;
  353.     int answer ;
  354.     static int ttyfd = -1 ;
  355.  
  356.     /*
  357.      *    Get a file descriptor to reference the
  358.      *    users tty terminal.
  359.      */
  360.  
  361.     if (ttyfd < 0)
  362.     {
  363.         if (isatty(0)) ttyfd = 0 ;
  364.         else if ((ttyfd = open("/dev/tty", O_RDWR)) == -1)
  365.         {
  366.             (void) fprintf(stderr, "Cannot open ") ;
  367.             perror("/dev/tty") ;
  368.             quit(1) ;
  369.         }
  370.     }
  371.  
  372.     /*
  373.      *    Read the tty for the user's answer.
  374.      */
  375.  
  376.     answer = 0 ;
  377.  
  378.     for (;;)
  379.     {
  380.         n = read(ttyfd, &ch, 1) ;
  381.         if (n == 1)
  382.         {
  383.             if (ch == '\r' || ch == '\n') break ;
  384.             if (answer == 0) answer = ch ;
  385.         }
  386.         if (n < 0)
  387.         {
  388.             perror("TTY") ;
  389.             quit(1) ;
  390.         }
  391.     }
  392.     
  393.     return(answer) ;
  394. }
  395.  
  396.  
  397.  
  398. /************************************************************
  399.  *    input - Get an input block.
  400.  ************************************************************/
  401.  
  402. input()
  403. {
  404.     register int n ;
  405.     register int i ;
  406.     register ushort *wp ;
  407.     int ch ;
  408.     static int eoi ;
  409.  
  410.     if (eoi) return(0) ;
  411.  
  412.     /*
  413.      *    Loop to read in a full input record.
  414.      */
  415.  
  416.     for (n = 0 ;;)
  417.     {
  418.         /*
  419.          *    Handle multi-volume input.
  420.          */
  421.  
  422.         if (infname && inrec == 0)
  423.         {
  424.             /*
  425.              *    If not the first volume of an n-volume set,
  426.              *    ask for confirmation before opening the file.
  427.              *
  428.              *    If he responds with (q), assume the last
  429.              *    volume has been read, and return end-of-file.
  430.              */
  431.  
  432.             if (++invol > 1)
  433.             {
  434.                 if (zcommand) (void) system(zcommand) ;
  435.  
  436.                 for (;;)
  437.                 {
  438.                     (void) fprintf(stderr,
  439.                         "Mount input volume #%d, hit <RETURN> (or 'q' to quit)? ",
  440.                         invol) ;
  441.  
  442.                     ch = confirm() ;
  443.             
  444.                     if (ch == 0) break ;
  445.  
  446.                     if (ch == 'q')
  447.                     {
  448.                         eoi = 1 ;
  449.                         goto done ;
  450.                     }
  451.                 }
  452.             
  453.  
  454.                 if (acommand) (void) system(acommand) ;
  455.             }
  456.             
  457.             /*
  458.              *    Open the file.
  459.              */
  460.  
  461.             if ((infd = open(infname, O_RDONLY)) == -1)
  462.             {
  463.                 (void) fprintf(stderr, "Cannot open ") ;
  464.                 perror(infname) ;
  465.                 quit(1) ;
  466.             }
  467.         }
  468.  
  469.         /*
  470.          *    Read in records until we get a full record, an
  471.          *    end-of-file, or an error.
  472.          */
  473.  
  474.         for (;;)
  475.         {
  476.             i = read(infd, (char*)inbuf + n, inbs - n) ;
  477.  
  478.             /*
  479.              *    Handle EOF.  If we are not doing multi-volume input
  480.              *    consider this the EOI.  If we are doing multi-volume
  481.              *    input, go back for the next volume.
  482.              */
  483.  
  484.             if (i == 0)
  485.             {
  486.                 (void) close(infd) ;
  487.  
  488.                 if (insize)
  489.                 {
  490.                     inrec = 0 ;
  491.                     break ;
  492.                 }
  493.  
  494.                 eoi = 1 ;
  495.                 goto done ;
  496.             }
  497.  
  498.             /*
  499.              *    Handle a file I/O error.
  500.              */
  501.  
  502.             if (i == -1)
  503.             {
  504.                 n = -1 ;
  505.                 perror("Input read error") ;
  506.                 (void) close(infd) ;
  507.                 return(-1) ;
  508.             }
  509.  
  510.             /*
  511.              *    A good read.  Add the bytes read this time to
  512.              *    the running total.  When we get a full record,
  513.              *    increment the volume record count.  When the
  514.              *    full volume size is reached, reset the record
  515.              *    position so we go back for another volume next
  516.              *    time.
  517.              */
  518.  
  519.             n += i ;
  520.  
  521.             if (n == inbs)
  522.             {
  523.                 if (++inrec == insize)
  524.                 {
  525.                     (void) close(infd) ;
  526.                     inrec = 0 ;
  527.                 }
  528.                 goto done ;
  529.             }
  530.         }
  531.     }
  532.  
  533.     /*
  534.      *    If byte swapping is in effect, swap all the
  535.      *    bytes in the current input buffer.
  536.      */
  537.  
  538. done:
  539.     if (inswap)
  540.     {
  541.         wp = inbuf ;
  542.         i = (n + 1) / 2 ;
  543.         while (--i >= 0)
  544.         {
  545.             *wp = SWAP(*wp) ;
  546.             wp++ ;
  547.         }
  548.     }
  549.  
  550.     return(n) ;
  551. }
  552.  
  553.  
  554.  
  555. /******************************************************************
  556.  *    fileinput - File input.
  557.  ******************************************************************/
  558.  
  559. fileinput()
  560. {
  561.     register int n ;
  562.  
  563.     n = input() ;
  564.  
  565.     if (n > 0)
  566.     {
  567.         intotal += n ;
  568.         if (n & 1) eofmagic = ODDMAGIC ;
  569.     }
  570.  
  571.     return((n + 1) / 2 - 1) ;
  572. }
  573.  
  574.  
  575.  
  576. /******************************************************************
  577.  *    inprocess - Input process
  578.  *
  579.  *    This procedure forks, then runs as a process reading from
  580.  *    the input device or pipe.
  581.  ******************************************************************/
  582.  
  583. inprocess()
  584. {
  585.     register char *sh ;
  586.     int rc ;
  587.     ushort *buf ;
  588.     ushort *ibuf ;
  589.     ushort *wp ;
  590.     int pfd[2] ;
  591.     int cfd[2] ;
  592.  
  593.     rsh = share_create(pfd, cfd, inbs, intank) ;
  594.     if (rsh == 0)
  595.     {
  596.         (void) fprintf(stderr, "Shared memory allocated failed\n") ;
  597.         quit(1) ;
  598.     }
  599.     
  600.     /*
  601.      *    Create the task.  Setup file descriptors so the
  602.      *    inprocess will die on SIGPIPE if the primary process
  603.      *    exits, but no SIGPIPE occurs to the promary process
  604.      *    when inprocess exits.
  605.      */
  606.  
  607.     while ((inpid = fork()) == -1) sleep(1) ;
  608.  
  609.     if (inpid == 0)
  610.     {
  611.         (void) close(1) ;
  612.         (void) close(cfd[0]) ;
  613.         (void) close(cfd[1]) ;
  614.  
  615.         /*
  616.          *    If input is done to a non-shared buffer,
  617.          *    allocate the buffer here.
  618.          */
  619.  
  620.         if (incopy)
  621.         {
  622.             buf = (ushort *)malloc(inbs) ;
  623.             if (buf == 0)
  624.             {
  625.                 (void) fprintf(stderr, "Not enough memory\n") ;
  626.                 exit(1) ;
  627.             }
  628.         }
  629.         else buf = 0 ;
  630.  
  631.         /*
  632.          *    Loop reading input blocks until done.
  633.          */
  634.         
  635.         sh = share_open(pfd) ;
  636.         assert(sh) ;
  637.  
  638.         for (;;)
  639.         {
  640.             /*
  641.              *    Get a block, read data into it, then pass it
  642.              *    to the data compression process.
  643.              */
  644.  
  645.             if (share_get(sh, (char**)&inbuf, &rc) <= 0) break ;
  646.  
  647.             if (buf)
  648.             {
  649.                 ibuf = inbuf ;
  650.                 inbuf = buf ;
  651.             }
  652.  
  653.             if ((rc = input()) <= 0) break ;
  654.  
  655.             if (buf)
  656.             {
  657.                 inbuf = ibuf ;
  658.                 (void) memcpy((char *)inbuf, (char *)buf, rc) ;
  659.             }
  660.  
  661.             if (share_put(sh, (char*)inbuf, rc) <= 0) break ;
  662.  
  663.             /*
  664.              *    In data compression mode with multi-volume
  665.              *    input, detect EOI here so as to avoid prompting
  666.              *    the user unnecessarily for another volume.
  667.              */
  668.  
  669.             if (action == 'e' && insize)
  670.             {
  671.                 wp = inbuf + rc / sizeof(ushort) ;
  672.  
  673.                 while (wp > inbuf && *--wp == 0) ;
  674.  
  675.                 if    (    wp >= inbuf
  676.                     &&    (*wp == ODDMAGIC || *wp == EVENMAGIC)
  677.                     &&    (wp == inbuf || *--wp == 0)
  678.                     &&    (wp == inbuf || *--wp == 0)
  679.                     &&    (wp == inbuf || *--wp == 0)
  680.                     )
  681.                     break ;
  682.             }
  683.         }
  684.  
  685. #if DEBUG >= 2
  686.         if (debug >= 2)
  687.         {
  688.             (void) fprintf(stderr, "Input child terminating normally\n") ;
  689.         }
  690. #endif
  691.  
  692.         /*
  693.          *    Exit the child when complete.
  694.          */
  695.  
  696.         share_close(sh) ;
  697.  
  698.         exit(0) ;
  699.     }
  700.  
  701.     /*
  702.      *    Initialize the shared memory interface in the
  703.      *    parent process.
  704.      */
  705.  
  706.     (void) close(pfd[1]) ;
  707.  
  708.     rsh = share_open(cfd) ;
  709. }
  710.  
  711.  
  712.  
  713. /************************************************************
  714.  *    shareinput - Do input from shared memory.
  715.  ************************************************************/
  716.  
  717. shareinput()
  718. {
  719.     int n ;
  720.  
  721.     if (inbuf) (void) share_put(rsh, (char*)inbuf, 0) ;
  722.  
  723.     if (share_get(rsh, (char**)&inbuf, &n) <= 0) return(-1) ;
  724.  
  725.     if (n > 0)
  726.     {
  727.         intotal += n ;
  728.         if (n & 1) eofmagic = ODDMAGIC ;
  729.     }
  730.  
  731.     return((n + 1) / 2 - 1) ;
  732. }
  733.  
  734.  
  735.  
  736. /***********************************************************
  737.  *    output - Output a block of data.
  738.  ***********************************************************/
  739.  
  740. output(nbyte)
  741. int nbyte ;                    /* Number of bytes to write */
  742. {
  743.     register ushort *wp ;
  744.     register int n ;
  745.     register int bsize ;
  746.  
  747.     /*
  748.      *    Open the output file if necessary.
  749.      */
  750.  
  751.     if (outfname && outrec == 0)
  752.     {
  753.         if (++outvol > 1)
  754.         {
  755.             if (zcommand) (void) system(zcommand) ;
  756.  
  757.             (void) fprintf(stderr,
  758.                 "Please mount output volume #%d, hit <RETURN> ",
  759.                 outvol) ;
  760.  
  761.             (void) confirm() ;
  762.  
  763.             if (acommand) (void) system(acommand) ;
  764.         }
  765.  
  766.         if ((outfd = open(outfname, O_WRONLY)) == -1)
  767.         {
  768.             (void) fprintf(stderr, "Cannot open ") ;
  769.             perror(outfname) ;
  770.             quit(1) ;
  771.         }
  772.     }
  773.     
  774.     /*
  775.      *    Swap output bytes if that option is selected.
  776.      */
  777.  
  778.     if (outswap)
  779.     {
  780.         n = nbyte / 2 + 1 ;
  781.         wp = outbuf ;
  782.         while (--n >= 0)
  783.         {
  784.             *wp = SWAP(*wp) ;
  785.             wp++ ;
  786.         }
  787.     }
  788.  
  789.     /*
  790.      *    Pad to a multiple of the given physical size if
  791.      *    that option is selected.
  792.      */
  793.  
  794.     if (nbyte < outbs && phys)
  795.     {
  796.         wp = &outbuf[nbyte/2] ;
  797.         bsize = (nbyte + phys - 1) / phys * phys ;
  798.         while (nbyte < bsize)
  799.         {
  800.             *wp++ = 0 ;
  801.             nbyte += 2 ;
  802.         }
  803.     }
  804.  
  805.     /*
  806.      *    Write the data and check for errors.
  807.      */
  808.  
  809.     n = write(outfd, (char*) outbuf, (int) nbyte) ;
  810.  
  811.     if (n < 0)
  812.     {
  813.         perror("Write error") ;
  814.         return(0) ;
  815.     }
  816.     
  817.     if (n != nbyte)
  818.     {
  819.         (void) fprintf(stderr,
  820.             "Write of %d bytes returned %d\n", nbyte, n) ;
  821.     }
  822.  
  823.     if (++outrec == outsize)
  824.     {
  825.         outrec = 0 ;
  826.         (void) close(outfd) ;
  827.     }
  828.  
  829.     return(outbs) ;
  830. }
  831.  
  832.  
  833.  
  834. /*****************************************************************
  835.  *    fileoutput - File oriented output routine.
  836.  *****************************************************************/
  837.  
  838. fileoutput(n)
  839. {
  840.     if (n < outbs && phys) outtotal += (n + phys - 1) / phys * phys ;
  841.     else outtotal += n ;
  842.  
  843.     return(output(n) / 2) ;
  844. }
  845.  
  846.  
  847.  
  848. /******************************************************************
  849.  *    outprocess - Output process
  850.  *
  851.  *    This procedure forks, then runs as a process writing to
  852.  *    the output device or pipe.
  853.  ******************************************************************/
  854.  
  855. outprocess()
  856. {
  857.     int pfd[2] ;
  858.     int cfd[2] ;
  859.     int wcount ;
  860.     int n ;
  861.     char *sh ;
  862.     ushort *obuf ;
  863.     ushort *buf ;
  864.  
  865.     wsh = share_create(pfd, cfd, outbs, outtank) ;
  866.     if (wsh == 0)
  867.     {
  868.         (void) fprintf(stderr, "Shared memory allocated failed\n") ;
  869.         quit(1) ;
  870.     }
  871.     
  872.     /*
  873.      *    Create the task.  Setup file descriptors so the
  874.      *    primary process will die on SIGPIPE if outprocess
  875.      *    exits, but no SIGPIPE occurs to outprocess when
  876.      *    the primary process exits.
  877.      */
  878.  
  879.     while ((outpid = fork()) == -1) sleep(1) ;
  880.  
  881.     if (outpid == 0)
  882.     {
  883.         (void) close(0) ;
  884.         (void) close(pfd[1]) ;
  885.  
  886.         sh = share_open(cfd) ;
  887.         assert(sh) ;
  888.  
  889.         if (outcopy)
  890.         {
  891.             buf = (ushort *)malloc(outbs) ;
  892.             if (buf == 0)
  893.             {
  894.                 (void) fprintf(stderr, "Not enough memory!\n") ;
  895.                 exit(1) ;
  896.             }
  897.         }
  898.         else buf = 0 ;
  899.  
  900.         for (;;)
  901.         {
  902.             if (share_get(sh, (char**)&outbuf, &wcount) <= 0) break ;
  903.  
  904.             if (buf)
  905.             {
  906.                 (void) memcpy((char *)buf, (char *)outbuf, wcount) ;
  907.                 obuf = outbuf ;
  908.                 outbuf = buf ;
  909.             }
  910.  
  911.             if (output(wcount) <= 0) break ;
  912.  
  913.             if (buf) outbuf = obuf ;
  914.  
  915.             if (share_put(sh, (char*) outbuf, 0) <= 0) break ;
  916.         }
  917.  
  918.         share_close(sh) ;
  919.  
  920.         exit(0) ;
  921.     }
  922.     
  923.     (void) close(cfd[0]) ;
  924.     (void) close(cfd[1]) ;
  925.  
  926.     wsh = share_open(pfd) ;
  927.  
  928.     (void) share_get(wsh, (char**)&outbuf, &n) ;
  929. }
  930.  
  931.  
  932.  
  933. /********************************************************
  934.  *    shareoutput - Shared memory output routine.
  935.  ********************************************************/
  936.  
  937. shareoutput(n)
  938. int n ;
  939. {
  940.     if (n < outbs && phys) outtotal += (n + phys - 1) / phys * phys ;
  941.     else outtotal += n ;
  942.  
  943.     if (share_put(wsh, (char*) outbuf, n) <= 0) return(0) ;
  944.  
  945.     if (share_get(wsh, (char**)&outbuf, &n) <= 0) return(0) ;
  946.  
  947.     return(outbs/2) ;
  948. }
  949.  
  950.  
  951.  
  952. /*************************************************************
  953.  *    check - keep track of the progress of the algorithm.
  954.  *************************************************************/
  955.  
  956. #if CHECK
  957. check(incount, outptr)
  958. int incount ;
  959. ushort *outptr ;
  960. {
  961.     ulong in ;
  962.     ulong out ;
  963.     float avg ;
  964.     float ratio ;
  965.  
  966.     static ulong lastin ;
  967.     static ulong lastout ;
  968.  
  969.     in = intotal - incount * sizeof(ushort) ;
  970.     out = outtotal + (long) outptr - (long) outbuf ;
  971.  
  972.     avg = 100.0 * (float) out / (float) in ;
  973.     ratio = 100.0 * (float) (out - lastout) / (float) (in - lastin) ;
  974.  
  975.     lastin = in ;
  976.     lastout = out ;
  977.  
  978. #if DEBUG >= 1
  979.     if (debug >= 1) (void) fprintf(stderr,
  980.         "Read: %-8ld Wrote: %-8ld Col: %-8ld Ratio: %6.2f%%  %6.2f%%\n",
  981.         in, out, collision, ratio, avg
  982.         ) ;
  983. #endif
  984. }
  985. #endif
  986.  
  987.  
  988.  
  989. /**************************************************************
  990.  *    compact - Compression algorithm.
  991.  **************************************************************/
  992.  
  993. compact()
  994. {
  995.     register ITEM *hp ;
  996.     register ITEM *sp ;
  997.     register ITEM **hpp ;
  998.     register ushort *inptr ;
  999.     register ushort *outptr ;
  1000.  
  1001.     register ulong ch ;
  1002.     register ulong code ;
  1003.     register ulong out ;
  1004.     register int obit ;
  1005.     register int osize ;
  1006.  
  1007.     register int incount ;
  1008.     register int outcount ;
  1009.     register ulong nitem ;
  1010.     register ulong mitem ;
  1011.     register ulong hashmask ;
  1012.  
  1013.     ITEM *itemtable ;
  1014.     ITEM **hashtable ;
  1015.  
  1016.     ITEM *ep ;
  1017.     long bitcount ;
  1018.     long blockcount ;
  1019.     long i ;
  1020.  
  1021.     ushort header[10] ;
  1022.  
  1023. #if CHECK
  1024.     long chkcount = CHECK ;
  1025. #endif
  1026.  
  1027.     /*
  1028.      *    If max output width is given, set maxitem accordingly.
  1029.      */
  1030.  
  1031.     maxitem = (1 << maxwidth) - MAXCHAR ;
  1032.  
  1033.     /*
  1034.      *    Reduce maxitem if necessary to fit into the requested
  1035.      *    maximum memory.
  1036.      */
  1037.  
  1038.     i = memory / (sizeof(ITEM) + sizeof(ITEM *)) ;
  1039.     if (maxitem > i) maxitem = i ;
  1040.  
  1041.     /*
  1042.      *    Set the hashtable to have the same approximate number
  1043.      *    of entries as in maxitem, rounded to the closest
  1044.      *    power of 2.
  1045.      */
  1046.  
  1047.     hashsize = HASHRATIO * maxitem ;
  1048.     while (i = hashsize & (hashsize - 1)) hashsize = i ;
  1049.     hashmask = hashsize - 1 ;
  1050.  
  1051. #if DEBUG >= 2
  1052.     if (debug >= 2)
  1053.     {
  1054.         (void) fprintf(stderr,
  1055.             "hashsize = %ld (%ldK), maxitem = %ld (%ldK)\n",
  1056.             hashsize, sizeof(ITEM *) * hashsize / 1024,
  1057.             maxitem, sizeof(ITEM) * maxitem / 1024) ;
  1058.     }
  1059. #endif
  1060.  
  1061.     /*
  1062.      *    Allocate hash table and item table.
  1063.      */
  1064.  
  1065.     itemtable = (ITEM *)malloc(maxitem * sizeof(ITEM)) ;
  1066.     hashtable = (ITEM **)malloc(hashsize * sizeof(ITEM *)) ;
  1067.  
  1068.     if (itemtable == 0 || hashtable == 0)
  1069.     {
  1070.         (void) fprintf(stderr,
  1071.             "Cannot allocate enough memory!\n") ;
  1072.         exit(2) ;
  1073.     }
  1074.  
  1075.     /*
  1076.      *    Initialize output.
  1077.      */
  1078.  
  1079.     outcount = outbs / 2 + 1 ;
  1080.     outptr = outbuf ;
  1081.     eofmagic = EVENMAGIC ;
  1082.  
  1083.     /*
  1084.      *    Each pass through the loop, compress one block
  1085.      *    of data.
  1086.      */
  1087.  
  1088.     for (;;)
  1089.     {
  1090.  
  1091. #if DEBUG >= 1
  1092.         if (debug >= 1) (void) fprintf(stderr, "\n") ;
  1093. #endif
  1094.  
  1095.         /*
  1096.          *    Initialize for a new scan.
  1097.          */
  1098.  
  1099.         (void) memset((char*)hashtable, 0, (int)(hashsize * sizeof(ITEM *))) ;
  1100.  
  1101.         nitem = 0 ;
  1102.  
  1103.         sp = &itemtable[0] ;
  1104.         ep = &itemtable[maxitem] ;
  1105.  
  1106.         out = 0 ;
  1107.         obit = 0 ;
  1108.         code = 0 ;
  1109.         osize = 17 ;
  1110.         bitcount = (1 << 16) ;
  1111.  
  1112.         blockcount = inrun / inbs + .5 ;
  1113.  
  1114.         /*
  1115.          *    Prepare the Magic number, and the maximum number
  1116.          *    of output codes for transmission.
  1117.          */
  1118.  
  1119.         mitem = maxitem ;
  1120.  
  1121.         header[0] = MAGIC ;
  1122.         header[1] = 17 ;
  1123.         header[2] = maxitem & 0xffff ;
  1124.         header[3] = maxitem >> 16 ;
  1125.  
  1126.         for (i = 0 ; i < 4 ; i++)
  1127.         {
  1128.             if (--outcount <= 0)
  1129.             {
  1130.                 if ((outcount = (*putout)(outbs)) == 0) return(1) ;
  1131.                 outptr = outbuf ;
  1132.             }
  1133.             *outptr++ = header[i] ;
  1134.         }
  1135.                 
  1136.         /*
  1137.          *    Read in the first input character of the run.
  1138.          */
  1139.  
  1140.         if ((incount = (*getin)()) < 0) goto endrun ;
  1141.  
  1142.         inptr = inbuf ;
  1143.         ch = *inptr++ ;
  1144.  
  1145.         /*
  1146.          *    Each pass through the loop, compress 1 or
  1147.          *    more input characters to output 1 compression
  1148.          *    code.
  1149.          */
  1150.  
  1151.         for (;;)
  1152.         {
  1153.  
  1154.             MARK(cmatch) ;
  1155.  
  1156.             code = ch + 1 ;
  1157.  
  1158. #if DEBUG >= 3
  1159.             if (debug >= 3) (void) fprintf(stderr,
  1160.                 "\nMatching char: %04x\n", ch) ;
  1161. #endif
  1162.  
  1163.             /*
  1164.              *    Each time through the loop, match the next
  1165.              *    input character if possible and continue.
  1166.              *    Exit when the match fails.
  1167.              */
  1168.  
  1169.             for (;;)
  1170.             {
  1171.  
  1172.                 /*
  1173.                  *    Read in the next input character.
  1174.                  */
  1175.  
  1176.                 if (--incount < 0)
  1177.                 {
  1178.  
  1179.                     if (--blockcount == 0)
  1180.                     {
  1181.                         incount = 0 ;
  1182.                         goto endrun ;
  1183.                     }
  1184. #if CHECK
  1185.                     if (--chkcount <= 0)
  1186.                     {
  1187.                         check(0, outptr) ;
  1188.                         chkcount = CHECK ;
  1189.                     }
  1190. #endif
  1191.                     if ((incount = (*getin)()) < 0) goto endrun ;
  1192.  
  1193.                     inptr = inbuf ;
  1194.                 }
  1195.  
  1196.                 ch = *inptr++ ;
  1197.  
  1198. #if DEBUG >= 3
  1199.                 if (debug >= 3) (void) fprintf(stderr,
  1200.                     "Read input char: %04x", ch) ;
  1201. #endif
  1202.  
  1203.                 /*
  1204.                  *    Search the hash table for the required
  1205.                  *    last code and current character.
  1206.                  */
  1207.  
  1208.                 hpp = &hashtable[HASHFUN(code, ch)] ;
  1209.  
  1210.                 for (;;)
  1211.                 {
  1212.                     if ((hp = *hpp) == 0) goto miss ;
  1213.  
  1214.                     if (hp->h_code == code && hp->h_char == ch) break ;
  1215.  
  1216.                     hpp = &hp->h_next ;
  1217. #if DEBUG >= 1
  1218.                     collision++ ;
  1219. #endif
  1220.                 }
  1221.  
  1222.                 code = hp - itemtable + MAXCHAR ;
  1223.  
  1224. #if DEBUG >= 3
  1225.                 if (debug >= 3) (void) fprintf(stderr,
  1226.                     "\tMatched code: %lx\n", (ulong) code) ;
  1227. #endif
  1228.             }
  1229.  
  1230.             /*
  1231.              *    Output the next code.
  1232.              */
  1233.  
  1234. miss:
  1235.             MARK(cout) ;
  1236.  
  1237.             out |= code << obit ;
  1238.             obit += osize ;
  1239.  
  1240.             if (--outcount <= 0)
  1241.             {
  1242.                 if ((outcount = (*putout)(outbs)) == 0) return(1) ;
  1243.                 outptr = outbuf ;
  1244.             }
  1245.  
  1246.             *outptr++ = out ;
  1247.  
  1248.             out >>= 16 ;
  1249.             obit -= 16 ;
  1250.  
  1251.             if (obit >= 16)
  1252.             {
  1253.                 
  1254.                 if (--outcount <= 0)
  1255.                 {
  1256.                     if ((outcount = (*putout)(outbs)) == 0) return(1) ;
  1257.                     outptr = outbuf ;
  1258.                 }
  1259.  
  1260.                 *outptr++ = out ;
  1261.  
  1262.                 if (obit > 16) out |= code >> (osize - obit) ;
  1263.  
  1264.                 out >>= 16 ;
  1265.                 obit -= 16 ;
  1266.             }
  1267.  
  1268. #if DEBUG >= 3
  1269.             if (debug >= 3) (void) fprintf(stderr,
  1270.                 "\nOutput code: %lx\n", (ulong) code) ;
  1271. #endif
  1272.  
  1273.             MARK(cbuild) ;
  1274.  
  1275.             sp->h_next = 0 ;
  1276.             sp->h_last = hpp ;
  1277.             *hpp = sp ;
  1278.  
  1279.             sp->h_code = code ;
  1280.             sp->h_char = ch ;
  1281.             sp->h_ref = 0 ;
  1282.             sp++ ;
  1283.  
  1284.             if (code >= MAXCHAR) itemtable[code - MAXCHAR].h_ref = 1 ;
  1285.  
  1286. #if DEBUG >= 3
  1287.             if (debug >= 3)
  1288.             {
  1289.                 (void) fprintf(stderr,
  1290.                     "Created compression code: %05lx ( %05lx %04x )\n",
  1291.                     sp - itemtable + MAXCHAR - 1, code, ch) ;
  1292.             }
  1293. #endif
  1294.             /*
  1295.              *    If we added a new entry to the table, expand
  1296.              *    the output bitsize if necessary.
  1297.              */
  1298.  
  1299.             if (nitem < mitem)
  1300.             {
  1301.                 MARK(calloc) ;
  1302.  
  1303.                 if (--bitcount == 0)
  1304.                 {
  1305.                     bitcount = 1 << osize ;
  1306.                     osize++ ;
  1307. #if DEBUG >= 2
  1308.                     if (debug >= 2) (void) fprintf(stderr,
  1309.                         "nitem = %d, osize = %d, bitcount = %d\n",
  1310.                         nitem, osize, bitcount) ;
  1311. #endif
  1312.                 }
  1313.  
  1314.                 if (++nitem != mitem) continue ;
  1315.             }
  1316.  
  1317.             /*
  1318.              *    When the compress item table has become full,
  1319.              *    find the least-recently-used leaf node and
  1320.              *    reallocate it.
  1321.              */
  1322.  
  1323.             MARK(cscan) ;
  1324.  
  1325.             for (;;)
  1326.             {
  1327.                 if (sp == ep) sp = itemtable ;
  1328.  
  1329.                 if (sp->h_ref == 0) break ;
  1330.  
  1331.                 if (sp->h_code >= MAXCHAR)
  1332.                 {
  1333.                     itemtable[sp->h_code - MAXCHAR].h_ref = 1 ;
  1334.                 }
  1335.  
  1336.                 sp->h_ref = 0 ;
  1337.                 sp++ ;
  1338.             }
  1339.  
  1340.             *sp->h_last = sp->h_next ;
  1341.             if (sp->h_next) sp->h_next->h_last = sp->h_last ;
  1342.         }
  1343.  
  1344.         /*
  1345.          *    Flush the output buffer, and add a few bytes
  1346.          *    of zero to guarantee synchronization.
  1347.          */
  1348.  
  1349. endrun:
  1350.         MARK(cend) ;
  1351.  
  1352. #if DEBUG >= 3
  1353.         if (debug >= 3) (void) fprintf(stderr,
  1354.             "\nOutput final code: %lx\n", (ulong) code) ;
  1355. #endif
  1356.  
  1357.         for (i = 0 ; i < 6 ; i++)
  1358.         {
  1359.             if (--outcount <= 0)
  1360.             {
  1361.                 if ((outcount = (*putout)(outbs)) == 0) return(1) ;
  1362.                 outptr = outbuf ;
  1363.             }
  1364.  
  1365.             out |= code << obit ;
  1366.  
  1367.             *outptr++ = out ;
  1368.  
  1369.             out >>= 16 ;
  1370.             code >>= 16 ;
  1371.         }
  1372.  
  1373.         if (incount < 0) break ;
  1374.  
  1375. #if CHECK
  1376.         check(incount, outptr) ;
  1377.         chkcount = CHECK ;
  1378. #endif
  1379.     }
  1380.  
  1381.     /*
  1382.      *    Add the EOF code at the end.
  1383.      */
  1384.  
  1385.     if (--outcount <= 0)
  1386.     {
  1387.         if ((outcount = (*putout)(outbs)) == 0) return(1) ;
  1388.         outptr = outbuf ;
  1389.     }
  1390.  
  1391.     *outptr++ = eofmagic ;
  1392.  
  1393.     if    (    outptr != outbuf
  1394.         &&    (*putout)((int) ((long)outptr-(long)outbuf)) == 0
  1395.         )
  1396.         return(1) ;
  1397.     
  1398. #if DEBUG >= 1
  1399.     if (debug >= 1) check(0, outbuf) ;
  1400. #endif
  1401.  
  1402.     if (!quiet && intotal != 0)
  1403.     {
  1404.         (void) fprintf(stderr,
  1405.             "Read %ld,  Wrote %ld,  Compression %6.2f%%\n",
  1406.             intotal, outtotal, 100.0 * (long)(intotal - outtotal) / intotal
  1407.             ) ;
  1408.     }
  1409.  
  1410. #if DEBUG >= 1
  1411.     if (!quiet && intotal > 1)
  1412.     {
  1413.         (void) fprintf(stderr,
  1414.             "Collisions: %ld, %6.2f %%\n",
  1415.             collision,
  1416.             (100.0 * 17.0 / 16.0 * collision) / (intotal-1)
  1417.             ) ;
  1418.     }
  1419. #endif
  1420.  
  1421.     return(0) ;
  1422. }
  1423.  
  1424.  
  1425.  
  1426. /***********************************************************
  1427.  *    expand - Expand previously compressed data.
  1428.  ***********************************************************/
  1429.  
  1430. expand()
  1431. {
  1432.     register DEC *sp ;
  1433.     register DEC *dp ;
  1434.     register ushort *bp ;
  1435.     register ushort *outptr ;
  1436.     register ushort *inptr ;
  1437.  
  1438.     register int ibit ;
  1439.     register ulong in ;
  1440.     register ulong ch ;
  1441.     register ulong code ;
  1442.     register ulong lastcode ;
  1443.     register int incount ;
  1444.     register int outcount ;
  1445.  
  1446.     int bitcount ;
  1447.     ulong maxcode ;
  1448.     DEC *dectable ;
  1449.     DEC *ep ;
  1450.  
  1451.     int isize ;
  1452.     ulong imask ;
  1453.     ushort *ip ;
  1454.     ushort *buffer ;
  1455.     int ic ;
  1456.     int i ;
  1457.     ulong skip ;
  1458.     ulong zskip ;
  1459.     int state ;
  1460.     ulong ncode ;
  1461.     int err ;
  1462.     int magic ;
  1463.     int nbyte ;
  1464.  
  1465.     ushort header[4] ;
  1466.  
  1467.     /*
  1468.      *    Initialize I/O buffers.
  1469.      */
  1470.  
  1471.     err = 0 ;
  1472.     incount = 0 ;
  1473.     magic = 0 ;
  1474.     outptr = outbuf ;
  1475.     outcount = outbs / 2 + 1 ;
  1476.     maxcode = 0 ;
  1477.     dectable = 0 ;
  1478.     buffer = 0 ;
  1479.  
  1480.     /*
  1481.      *    Each time through the loop, process a complete
  1482.      *    block of data.
  1483.      */
  1484.  
  1485.     state = 4 ;
  1486.  
  1487.     for (;;)
  1488.     {
  1489.  
  1490.         /*
  1491.          *    Synchronize to the beginning of a new block of data.
  1492.          *
  1493.          *    The file begins immediately with a magic number.
  1494.          *
  1495.          *    Thereafter, blocks of decompression data are delimited
  1496.          *    by at least two bytes of zero, followed by the two
  1497.          *    byte magic number.
  1498.          */
  1499.  
  1500.         MARK(esync) ;
  1501.  
  1502.         skip = 0 ;
  1503.         zskip = 0 ;
  1504.  
  1505.         for (;;)
  1506.         {
  1507.             if (--incount < 0)
  1508.             {
  1509.                 if ((incount = (*getin)()) < 0) break ;
  1510.                 inptr = inbuf ;
  1511.             }
  1512.             in = *inptr++ ;
  1513.  
  1514.             if (in == 0)
  1515.             {
  1516.                 if (state <= 4) state++ ;
  1517.                 else zskip += sizeof(ushort) ;
  1518.             }
  1519.             else
  1520.             {
  1521.                 if (state >= 2)
  1522.                 {
  1523.                     if (in == MAGIC)
  1524.                     {
  1525.                         magic = 1 ;
  1526.                         break ;
  1527.                     }
  1528.                     if (in == (SWAP(MAGIC) & 0xffff))
  1529.                     {
  1530.                         if (!quiet) (void) fprintf(stderr,
  1531.                             "Automatically reversing byte order!\n") ;
  1532.  
  1533.                         inswap = !inswap ;
  1534.                         outswap = !outswap ;
  1535.  
  1536.                         ip = inptr ;
  1537.                         ic = incount ;
  1538.                         while (--ic >= 0)
  1539.                         {
  1540.                             *ip = SWAP(*ip) ;
  1541.                             ip++ ;
  1542.                         }
  1543.                         magic = 1 ;
  1544.                         break ;
  1545.                     }
  1546.                     if ((in == ODDMAGIC || in == EVENMAGIC) && magic)
  1547.                     {
  1548.                         eofmagic = in ;
  1549.                         magic = 2 ;
  1550.                         incount = -1 ;
  1551.                         break ;
  1552.                     }
  1553.                 }
  1554.                 skip += sizeof(ushort) ;
  1555.                 state = 0 ;
  1556.             }
  1557.         }
  1558.  
  1559.         /*
  1560.          *    Mention that data was skipped.
  1561.          */
  1562.  
  1563.         if (skip != 0 || zskip != 0 && incount >= 0)
  1564.         {
  1565.             (void) fprintf(stderr,
  1566.                 "Warning: %d bytes of unintelligible data skipped!\n",
  1567.                 skip + zskip) ;
  1568.         }
  1569.  
  1570.         if (incount < 0)
  1571.         {
  1572.             if (magic == 0) (void) fprintf(stderr,
  1573.                 "Warning: Magic number not found!\n") ;
  1574.             if (magic == 1) (void) fprintf(stderr,
  1575.                 "Warning: Old style EOF encountered!\n") ;
  1576.             goto eof ;
  1577.         }
  1578.             
  1579.         /*
  1580.          *    Get the maximum code present in the data.
  1581.          */
  1582.  
  1583.         for (i = 1 ; i < 4 ; i++)
  1584.         {
  1585.             if (--incount < 0)
  1586.             {
  1587.                 if ((incount = (*getin)()) < 0)
  1588.                 {
  1589.                     (void) fprintf(stderr, "EOF in header!\n") ;
  1590.                     err = 1 ;
  1591.                     goto eof ;
  1592.                 }
  1593.                 inptr = inbuf ;
  1594.             }
  1595.             header[i] = *inptr++ ;
  1596.         }
  1597.  
  1598.         code = header[3] ;
  1599.         code <<= 16 ;
  1600.         code |= header[2] ;
  1601.  
  1602. #if DEBUG >= 2
  1603.         if (debug >= 2) (void) fprintf(stderr,
  1604.             "Read header, nbits=%d, maxitem=%d\n", header[1], code) ;
  1605. #endif
  1606.  
  1607.         /*
  1608.          *    Allocate the required memory.
  1609.          */
  1610.  
  1611.         if (maxcode != code)
  1612.         {
  1613.  
  1614.             dectable = dectable
  1615.                 ?    (DEC *) realloc((char*) dectable, code * sizeof(DEC))
  1616.                 :    (DEC *) malloc(code * sizeof(DEC))
  1617.                 ;
  1618.  
  1619.             buffer = buffer
  1620.                 ?    (ushort *) realloc((char*)buffer, code * sizeof(ushort))
  1621.                 :    (ushort *) malloc(code * sizeof(ushort))
  1622.                 ;
  1623.  
  1624.             if (dectable == 0 || buffer == 0)
  1625.             {
  1626.                 (void) fprintf(stderr,
  1627.                     "Cannot get enough memory to decode %d items\n", code) ;
  1628.                 exit(1) ;
  1629.             }
  1630.  
  1631.             maxcode = code ;
  1632.         }
  1633.  
  1634.         sp = &dectable[0] ;
  1635.         ep = &dectable[maxcode] ;
  1636.  
  1637.         /*
  1638.          *    Initialize to decompress this block of data.
  1639.          */
  1640.  
  1641.         in = 0 ;
  1642.         ibit = 0 ;
  1643.         ncode = 0 ;
  1644.         bp = buffer ;
  1645.  
  1646.         isize = 17 ;
  1647.         bitcount = (1 << 16) ;
  1648.         imask = 0x1ffff ;
  1649.  
  1650.         /*
  1651.          *    Read in the first item, which must be a
  1652.          *    single character.
  1653.          */
  1654.  
  1655.         do
  1656.         {
  1657.             if (--incount < 0)
  1658.             {
  1659.                 if ((incount = (*getin)()) < 0)
  1660.                 {
  1661.                     (void) fprintf(stderr, "Premature eof!\n") ;
  1662.                     err = 1 ;
  1663.                     goto eof ;
  1664.                 }
  1665.                 inptr = inbuf ;
  1666.             }
  1667.             in |= *inptr++ << ibit ;
  1668.             ibit += 16 ;
  1669.         } while (ibit < 17) ;
  1670.  
  1671.         code = in & imask ;
  1672.  
  1673.         if (code == 0)
  1674.         {
  1675.             state = 0 ;
  1676.             continue ;
  1677.         }
  1678.  
  1679.         in >>= 17 ;
  1680.         ibit -= 17 ;
  1681.  
  1682.         if (code == 0)
  1683.         {
  1684.             (void) fprintf(stderr, "Null compression block!\n") ;
  1685.             break ;
  1686.         }
  1687.  
  1688.         ch = code - 1 ;
  1689.  
  1690. #if DEBUG >= 3
  1691.         if (debug >= 3) (void) fprintf(stderr,
  1692.             "First input code: %05lx output as < %04x >\n", code, ch) ;
  1693. #endif
  1694.  
  1695.         if (--outcount <= 0)
  1696.         {
  1697.             if ((outcount = (*putout)(outbs)) == 0) return(1) ;
  1698.             outptr = outbuf ;
  1699.         }
  1700.         
  1701.         *outptr++ = ch ;
  1702.  
  1703.         /*
  1704.          *    Each time through the loop, read and process one
  1705.          *    compressed item code.
  1706.          */
  1707.  
  1708.         MARK(eloop) ;
  1709.  
  1710.         for (;;)
  1711.         {
  1712.             lastcode = code ;
  1713.  
  1714.             /*
  1715.              *    Expand the input bitsize if necessary.
  1716.              */
  1717.  
  1718.             if (ncode < maxcode)
  1719.             {
  1720.                 MARK(ealloc) ;
  1721.  
  1722.                 if (--bitcount == 0)
  1723.                 {
  1724.                     bitcount = 1 << isize ;
  1725.                     isize++ ;
  1726.                     imask += imask + 1 ;
  1727. #if DEBUG >= 2
  1728.                     if (debug >= 2) (void) fprintf(stderr,
  1729.                         "ncode = %d, isize = %d, bitcount = %d\n",
  1730.                         ncode, isize, bitcount) ;
  1731. #endif
  1732.                 }
  1733.                 ncode++ ;
  1734.             }
  1735.  
  1736.             /*
  1737.              *    If the table is full, find the oldest leaf node
  1738.              *    and reallocate it.
  1739.              */
  1740.  
  1741.             else
  1742.             {
  1743.                 MARK(escan) ;
  1744.  
  1745.                 for (;;)
  1746.                 {
  1747.                     if (sp == ep) sp = dectable ;
  1748.                     if (sp->d_ref == 0) break ;
  1749.                     if (sp->d_code >= MAXCHAR)
  1750.                     {
  1751.                         dectable[sp->d_code - MAXCHAR].d_ref = 1 ;
  1752.                     }
  1753.                     sp->d_ref = 0 ;
  1754.                     sp++ ;
  1755.                 }
  1756.             }
  1757.  
  1758.             /*
  1759.              *    Read in the next compression code.
  1760.              */
  1761.  
  1762.             MARK(eread) ;
  1763.  
  1764.             if (--incount < 0)
  1765.             {
  1766.                 if ((incount = (*getin)()) < 0)
  1767.                 {
  1768.                     (void) fprintf(stderr, "Premature eof\n") ;
  1769.                     err = 1 ;
  1770.                     goto eof ;
  1771.                 }
  1772.                 inptr = inbuf ;
  1773.             }
  1774.  
  1775.             in |= *inptr++ << ibit ;
  1776.             ibit += 16 ;
  1777.  
  1778.             if (ibit >= isize)
  1779.             {
  1780.                 code = in & imask ;
  1781.  
  1782.                 in >>= isize ;
  1783.                 ibit -= isize ;
  1784.             }
  1785.             else
  1786.             {
  1787.                 if (--incount < 0)
  1788.                 {
  1789.                     if ((incount = (*getin)()) < 0)
  1790.                     {
  1791.                         (void) fprintf(stderr, "Premature eof\n") ;
  1792.                         err = 1 ;
  1793.                         goto eof ;
  1794.                     }
  1795.                     inptr = inbuf ;
  1796.                 }
  1797.  
  1798.                 if (ibit <= 16)
  1799.                 {
  1800.                     in |= (ulong) *inptr++ << ibit ;
  1801.  
  1802.                     code = in & imask ;
  1803.  
  1804.                     in >>= isize ;
  1805.                     ibit -= isize - 16 ;
  1806.                 }
  1807.                 else
  1808.                 {
  1809.                     in |= (ulong) *inptr << ibit ;
  1810.  
  1811.                     code = in & imask ;
  1812.  
  1813.                     in >>= isize ;
  1814.                     in |= (ulong) *inptr++ >> (isize - ibit) ;
  1815.  
  1816.                     ibit -= isize - 16 ;
  1817.                 }
  1818.             }
  1819.  
  1820. #if DEBUG >= 4
  1821.             if (debug >= 4) (void) fprintf(stderr,
  1822.                 "Read input code: %05lx\n", code) ;
  1823. #endif
  1824.             /*
  1825.              *    If a zero code is detected, start a new
  1826.              *    decompression pass.
  1827.              *
  1828.              *    If a character code is detected, output it.
  1829.              */
  1830.  
  1831.             MARK(eexpand) ;
  1832.  
  1833.             if (code < MAXCHAR)
  1834.             {
  1835.                 if (code == 0) break ;
  1836.                 ch = code ;
  1837.             }
  1838.  
  1839.             /*
  1840.              *    Expand a compression code.
  1841.              *
  1842.              *    If the code is the next one to be allocated, 
  1843.              *    then it was allocated by the compression program
  1844.              *    already to be the lastcode + the first character
  1845.              *    of the last code.
  1846.              *
  1847.              *    Also check for an out-of-range decompression
  1848.              *    code.  Signal an error in this case.
  1849.              */
  1850.  
  1851.             else
  1852.             {
  1853.                 if (code - MAXCHAR >= ncode)
  1854.                 {
  1855.                     (void) fprintf(stderr,
  1856.                         "Decompress error - attempting resync\n") ;
  1857.                     break ;
  1858.                 }
  1859.  
  1860.                 dp = &dectable[code - MAXCHAR] ;
  1861.  
  1862.                 if (dp == sp)
  1863.                 {
  1864.  
  1865.                     if (sp - dectable == lastcode - MAXCHAR)
  1866.                     {
  1867.                         (void) fprintf(stderr,
  1868.                             "Nasty decompress error - attempting resync\n") ;
  1869.                         break ;
  1870.                     }
  1871.  
  1872.                     *bp++ = ch ;
  1873.  
  1874.                     ch = lastcode ;
  1875.  
  1876.                     if (ch >= MAXCHAR)
  1877.                     {
  1878.  
  1879.                         dp = &dectable[ch - MAXCHAR] ;
  1880.  
  1881.                         for (;;)
  1882.                         {
  1883.                             *bp++ = dp->d_char ;
  1884.                             ch = dp->d_code ;
  1885.                             if (ch < MAXCHAR) break ;
  1886.                             dp = &dectable[ch - MAXCHAR] ;
  1887.                         }
  1888.                     }
  1889.                 }
  1890.  
  1891.                 else
  1892.                 {
  1893.                     for (;;)
  1894.                     {
  1895.                         *bp++ = dp->d_char ;
  1896.                         ch = dp->d_code ;
  1897.                         if (ch < MAXCHAR) break ;
  1898.                         dp = &dectable[ch - MAXCHAR] ;
  1899.                     }
  1900.                 }
  1901.             }
  1902.             
  1903.             ch -= 1 ;
  1904.  
  1905.             /*
  1906.              *    Output the compression code data.
  1907.              */
  1908.  
  1909.             MARK(eout) ;
  1910.  
  1911. #if DEBUG >= 3
  1912.             if (debug >= 3)
  1913.             {
  1914.                 ushort *wp ;
  1915.                 (void) fprintf(stderr, "Expanded code %05lx to <", code) ;
  1916.                 wp = bp ;
  1917.                 *wp++ = ch ;
  1918.                 do
  1919.                 {
  1920.                     (void) fprintf(stderr, " %04x", *--wp) ;
  1921.                 } while (wp != buffer) ;
  1922.                 (void) fprintf(stderr, " >\n") ;
  1923.             }
  1924. #endif
  1925.  
  1926.             if (--outcount <= 0)
  1927.             {
  1928.                 if ((outcount = (*putout)(outbs)) == 0) return(1) ;
  1929.                 outptr = outbuf ;
  1930.             }
  1931.             
  1932.             *outptr++ = ch ;
  1933.  
  1934.             while (bp != buffer)
  1935.             {
  1936.                 if (--outcount <= 0)
  1937.                 {
  1938.                     if ((outcount = (*putout)(outbs)) == 0) return(1) ;
  1939.                     outptr = outbuf ;
  1940.                 }
  1941.  
  1942.                 *outptr++ = *--bp ;
  1943.             }
  1944.  
  1945.             /*
  1946.              *    Create a new code from the input data.
  1947.              */
  1948.  
  1949.             MARK(ebuild) ;
  1950.  
  1951.             sp->d_code = lastcode ;
  1952.             sp->d_char = ch ;
  1953.             sp->d_ref = 0 ;
  1954.             sp++ ;
  1955.  
  1956.             if (lastcode >= MAXCHAR) dectable[lastcode - MAXCHAR].d_ref = 1 ;
  1957.  
  1958. #if DEBUG >= 3
  1959.             if (debug >= 3)
  1960.             {
  1961.                 (void) fprintf(stderr,
  1962.                     "Created compression code: %05lx ( %05lx %04x )\n",
  1963.                     sp - dectable + MAXCHAR - 1, lastcode, ch) ;
  1964.             }
  1965. #endif
  1966.         }
  1967.  
  1968.         state = 0 ;
  1969.     }
  1970.  
  1971. eof:
  1972.     nbyte = (long)outptr - (long)outbuf ;
  1973.     if (eofmagic == ODDMAGIC) nbyte-- ;
  1974.  
  1975.     if (nbyte && (*putout)(nbyte) == 0) return(1) ;
  1976.  
  1977.     if (!quiet && intotal != 0)
  1978.     {
  1979.         (void) fprintf(stderr,
  1980.         "Read %ld,  Wrote %ld,  Expansion %6.2f%%\n",
  1981.         intotal, outtotal,
  1982.         100.0 * (long)(outtotal - intotal) / intotal) ;
  1983.     }
  1984.  
  1985.     return(err) ;
  1986. }
  1987.  
  1988.  
  1989.  
  1990. /**************************************************************
  1991.  *    main - main program.
  1992.  **************************************************************/
  1993.  
  1994. main(argc, argv)
  1995. int argc ;
  1996. char **argv ;
  1997. {
  1998.     register int i ;
  1999.     register int c ;
  2000.     register int err ;
  2001.     register int rs ;
  2002.     register char *p ;
  2003.     extern char *optarg ;
  2004.     extern int optind ;
  2005.  
  2006.     /*
  2007.      *    Set default parameters.
  2008.      */
  2009.  
  2010.     infd = 0 ;
  2011.     outfd = 1 ;
  2012.  
  2013.     inbs = BUFSIZ ;
  2014.     outbs = BUFSIZ ;
  2015.  
  2016.     memory = MEMORY ;
  2017.     maxwidth = 17 ;
  2018.  
  2019.     inrun = INRUN ;
  2020.  
  2021.     /*
  2022.      *    If command begins with 'e' or 'u', expand the
  2023.      *    input file.  Otherwise compress it.
  2024.      */
  2025.  
  2026.     p = argv[0] ;
  2027.     action = *p ;
  2028.     while (*p) if (*p++ == '/') action = *p ;
  2029.  
  2030.     if (action == 'u') action = 'e' ;
  2031.     else if (action != 'e') action = 'c' ;
  2032.  
  2033. #if DEBUG >= 1
  2034.     debug = DEBUG ;
  2035. #endif
  2036.  
  2037.     /*
  2038.      *    Unpack parameters.
  2039.      */
  2040.  
  2041.     err = 0 ;
  2042.  
  2043.     for (;;)
  2044.     {
  2045.         c = getopt(argc, argv, "a:b:B:cd:ef:F:lm:n:N:p:qr:R:sSt:T:uvw:xXz:") ;
  2046.  
  2047.         if (c == EOF) break ;
  2048.  
  2049.         switch (c)
  2050.         {
  2051.  
  2052.             /*
  2053.              *    Media setup command to be performed before
  2054.              *    first open.
  2055.              */
  2056.             
  2057.             case 'a':
  2058.                 acommand = optarg ;
  2059.                 break ;
  2060.             
  2061.             /*
  2062.              *    Input/output block size.
  2063.              */
  2064.  
  2065.             case 'b':
  2066.                 inbs = getval(optarg, 'k') ;
  2067.                 if (inbs <= 2 || (inbs & 1)) err++ ;
  2068.                 break ;
  2069.  
  2070.             case 'B':
  2071.                 outbs = getval(optarg, 'k') ;
  2072.                 if (outbs <= 2 || (outbs & 1)) err++ ;
  2073.                 break  ;
  2074.  
  2075.             /*
  2076.              *    Compress or expand action.
  2077.              */
  2078.  
  2079.             case 'c':
  2080.             case 'e':
  2081.                 action = c ;
  2082.                 break ;
  2083.  
  2084.             /*
  2085.              *    Debug level.
  2086.              */
  2087.  
  2088. #if DEBUG >= 1
  2089.             case 'd':
  2090.                 debug = atoi(optarg) ;
  2091.                 if (debug > DEBUG) err++ ;
  2092.                 break ;
  2093. #endif
  2094.  
  2095.             /*
  2096.              *    Input/Output file name.
  2097.              */
  2098.  
  2099.             case 'f':
  2100.                 infname = optarg ;
  2101.                 break ;
  2102.             
  2103.             case 'F':
  2104.                 outfname = optarg ;
  2105.                 break ;
  2106.             
  2107.             /*
  2108.              *    Lock process into memory.
  2109.              */
  2110.             
  2111.             case 'l':
  2112.                 memlock = 1 ;
  2113.                 break ;
  2114.  
  2115.             /*
  2116.              *    Amount of memory to use.
  2117.              */
  2118.  
  2119.             case 'm':
  2120.                 memory = getval(optarg, 'k') ;
  2121.                 if (memory < 1) err++ ;
  2122.                 break ;
  2123.  
  2124.             /*
  2125.              *    Physical record size.  Causes the last output
  2126.              *    record to be padded with zeros to the next
  2127.              *    multiple of this size if necessary.
  2128.              */
  2129.  
  2130.             case 'p':
  2131.                 phys = getval(optarg, 'k') ;
  2132.                 if (phys <= 2 || (phys & 1)) err++ ;
  2133.                 break ;
  2134.             
  2135.             /*
  2136.              *    Quiet mode.
  2137.              */
  2138.             
  2139.             case 'q':
  2140.                 quiet = 1 ;
  2141.                 break ;
  2142.             
  2143.             /*
  2144.              *    Number of input/output records in volume.
  2145.              */
  2146.  
  2147.             case 'n':
  2148.                 insize = getval(optarg, 'k') ;
  2149.                 if (insize < 1) err++ ;
  2150.                 break ;
  2151.                 
  2152.             case 'N':
  2153.                 outsize = getval(optarg, 'k') ;
  2154.                 if (outsize < 1) err++ ;
  2155.                 break  ;
  2156.  
  2157.             /*
  2158.              *    Maximum run length.
  2159.              */
  2160.  
  2161.             case 'r':
  2162.                 inrun = getval(optarg, 0) ;
  2163.                 if (inrun < 5) err++ ;
  2164.                 break ;
  2165.  
  2166.             /*
  2167.              *    Swap input or output bytes.
  2168.              */
  2169.  
  2170.             case 's':
  2171.                 inswap++ ;
  2172.                 break ;
  2173.             
  2174.             case 'S':
  2175.                 outswap++ ;
  2176.                 break ;
  2177.             
  2178.             /*
  2179.              *    Tank size.
  2180.              */
  2181.             
  2182.             case 't':
  2183.                 intank = getval(optarg, 0) ;
  2184.                 if (intank < 2 || intank > 500) err++ ;
  2185.                 break ;
  2186.  
  2187.             case 'T':
  2188.                 outtank = getval(optarg, 0) ;
  2189.                 if (outtank < 2 || outtank > 500) err++ ;
  2190.                 break ;
  2191.             
  2192.             /*
  2193.              *    Uncompress.
  2194.              */
  2195.             
  2196.             case 'u':
  2197.                 action = 'e' ;
  2198.                 break ;
  2199.  
  2200.             /*
  2201.              *    Version.
  2202.              */
  2203.             
  2204.             case 'v':
  2205. #if DEBUG >= 1
  2206.                 (void) fprintf(stderr, "%s (debug %d)\n", VERSION, DEBUG) ;
  2207. #else
  2208.                 (void) fprintf(stderr, "%s\n", VERSION) ;
  2209. #endif
  2210.                 return(0) ;
  2211.  
  2212.             /*
  2213.              *    Maximum output bit width.
  2214.              */
  2215.             
  2216.             case 'w':
  2217.                 maxwidth = getval(optarg, 0) ;
  2218.                 if (maxwidth < 17 || maxwidth > 24) err++ ;
  2219.                 break ;
  2220.  
  2221.             /*
  2222.              *    Read/Write data to/from non-shared memory buffers
  2223.              *    to avoid driver problems.
  2224.              */
  2225.  
  2226.             case 'x':
  2227.                 incopy = 1 ;
  2228.                 break ;
  2229.  
  2230.             case 'X':
  2231.                 outcopy = 1 ;
  2232.                 break ;
  2233.  
  2234.             /*
  2235.              *    Command to be performed after last close.
  2236.              */
  2237.  
  2238.             case 'z':
  2239.                 zcommand = optarg ;
  2240.                 break ;
  2241.  
  2242.             default:
  2243.                 err++ ;
  2244.         }
  2245.     }
  2246.  
  2247.     /*
  2248.      *    Check parameter consistency.
  2249.      */
  2250.  
  2251.     if (insize && !infname)
  2252.     {
  2253.         (void) fprintf(stderr, "-n requires -f\n") ;
  2254.         err++ ;
  2255.     }
  2256.     
  2257.     if (outsize && !outfname)
  2258.     {
  2259.         (void) fprintf(stderr, "-N requires -F\n") ;
  2260.         err++ ;
  2261.     }
  2262.             
  2263.     /*
  2264.      *    Print the USAGE message.
  2265.      */
  2266.  
  2267.     if (optind != argc || err)
  2268.     {
  2269.         (void) fprintf(stderr, "Usage: %s %s%s%s", argv[0],
  2270.             "[-celqsSvxX] [-a cmd] [-b cbs] [-B ebs] [-f cfile] [-F efile]\n",
  2271.             "\t[-m memory] [-n cblks] [-N eblks] [-p outpad] [-r runsize]\n",
  2272.             "\t[-t cbuf] [-T ebuf] [-w width] [-z cmd]\n") ;
  2273.         exit(2) ;
  2274.     }
  2275.     
  2276.     /*
  2277.      *    Adjust compression parameters.
  2278.      */
  2279.  
  2280.     if (action == 'c')
  2281.     {
  2282.         long i ;
  2283.         char *p ;
  2284.  
  2285.         /*
  2286.          *    Switch parameters around if necessary so the lower
  2287.          *    case options refer to the compressed file, and the
  2288.          *    upper case letters refer to the expanded file.
  2289.          */
  2290.  
  2291.         if (phys == 0) phys = 512 ;
  2292.  
  2293.         i = insize ; insize = outsize ; outsize = i ;
  2294.         i = inbs ; inbs = outbs ; outbs = i ;
  2295.         i = intank ; intank = outtank ; outtank = i ;
  2296.         i = inswap ; inswap = outswap ; outswap = i ;
  2297.         i = incopy ; incopy = outcopy ; outcopy = i ;
  2298.         p = infname ; infname = outfname ; outfname = p ;
  2299.     }
  2300.     
  2301.     /*
  2302.      *    Adjust output block size to correspond with
  2303.      *    the requested output padding.
  2304.      */
  2305.  
  2306.     if (phys)
  2307.     {
  2308.         if (outbs < phys) outbs = phys ;
  2309.         else outbs = (outbs + phys - 1) / phys * phys ;
  2310.     }
  2311.     
  2312.     /*
  2313.      *    Execute setup command.
  2314.      */
  2315.     
  2316.     if (acommand) (void) system(acommand) ;
  2317.  
  2318.     /*
  2319.      *    Setup input operation through shared memory.
  2320.      */
  2321.     
  2322.     if (intank)
  2323.     {
  2324.         inprocess() ;
  2325.         getin = shareinput ;
  2326.     }
  2327.     else
  2328.     {
  2329.         inbuf = (ushort *) malloc((unsigned) inbs+1) ;
  2330.         getin = fileinput ;
  2331.     }
  2332.     
  2333.     /*
  2334.      *    Setup output operation through shared memory.
  2335.      */
  2336.     
  2337.     if (outtank)
  2338.     {
  2339.         outprocess() ;
  2340.         putout = shareoutput ;
  2341.     }
  2342.     else
  2343.     {
  2344.         outbuf = (ushort *) malloc((unsigned) outbs) ;
  2345.         putout = fileoutput ;
  2346.     }
  2347.  
  2348.     /*
  2349.      *    Lock process into memory.
  2350.      */
  2351.     
  2352.     if (memlock && plock(PROCLOCK) == -1)
  2353.     {
  2354.         (void) perror("Cannot lock process in memory") ;
  2355.         return(2) ;
  2356.     }
  2357.         
  2358.     /*
  2359.      *    Setup to gracefully exit.
  2360.      */
  2361.  
  2362.     for (i = 0 ; sig[i] ; i++)
  2363.     {
  2364.         if (signal(sig[i], SIG_IGN) != SIG_IGN)
  2365.             (void) signal(sig[i], quit) ;
  2366.     }
  2367.  
  2368.     /*
  2369.      *    Compress or expand input data.
  2370.      */
  2371.  
  2372.     rs = action == 'c' ? compact() : expand() ;
  2373.  
  2374.     quit(rs) ;
  2375.  
  2376.     return(0) ;
  2377. }
  2378.